2023CCPC 国赛（秦皇岛） 题解

The 2nd Universal Cup. Stage 9: Qinhuangdao

A - Make SYSU Great Again I

Solution

难得构造题签到，蛇形走位就好了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 5;
ll n, k;
ll dx[2] = {0, 1};
ll dy[2] = {1, 0};
int main(){
    ios::sync_with_stdio(false);
    map<pair<int, int>, int> mp;
    cin >> n >> k;
    ll x = 1, y = 1, cnt = 0;
    for(int i = 1; i <= 2 * n - 1; i ++){
        mp[{x, y}] = 1;
        cnt ++;
        cout << x << " " << y << '\n';
        x += dx[cnt & 1];
        y += dy[cnt & 1];
    }
    mp[{1, n}] = 1;
    cout << 1 << " " << n << "\n";
    cnt ++;
    if(cnt == k) return 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(!mp[{i, j}]) cout << i << " " << j << "\n", cnt ++;
            mp[{i, j}] = 1;
            if(cnt == k) return 0;
        }
    }
    return 0;
}

D - Yet Another Coffee

Question

$n$ 个物品，$m$ 个优惠券，第 $i$ 个物品的价格为 $a_i$，每个优惠券只能在 $[1,r_i]$ 整个区间内使用一次，每次减少 $w_i$ 的价格，价格可以被减成负数，对每个 $k=1\sim n$ 求恰好买 $k$ 个物品的最小花费

Solution

我用了一种和std不太一样的做法

可以通过归纳 + 反证得出对于 $k+1$ 个购买的物品，实际上就是在 $k$ 个购买物品的基础上再购买一个，如果我们购买 $k$ 个物品的集合为 $\{S\}$ 可以维护 $S$ 中最靠前的物品 $j$，那么接下来选择的一个物品要么就是在 $1\sim j-1$，要么就是在 $j+1\sim n$

贪心可以得出，我们可以在 $j$ 处使用完所有优惠券，我们先预处理出买第 $i$ 个物品时，把能用的优惠券全用完的优惠价格 $g[i]$

• 如果考虑接下来一个选择 $1\sim j-1$，那么我们只需要找 $a[i]-g[i]$ 最小值，作为新的 $j$，产生的代价为 $a[i]-g[i]+g[j]$，这可以用一个预处理来维护
• 如果考虑 $j+1\sim n$，那么只需要找到 $j+1\sim n$ 最小的 $a[i]$ 且 $i$ 不在 $S$ 中，这可以用一个堆来维护

总时间复杂度为 $O(n+k\log n)$

Code

#include <bits/stdc++.h>

using ll = long long;
const ll INF = 1e17;

void solve() {
    int n, m; std::cin >> n >> m;
    std::vector<ll> a(n + 1), g(n + 1, 0);
    std::vector<std::pair<int, ll>> p(m + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= m; i++) std::cin >> p[i].first >> p[i].second;

    sort(p.begin() + 1, p.end());

    ll sum = 0;
    for (int i = n, j = m; i ; i--) {
        while (j > 0 && p[j].first >= i) sum += p[j--].second;
        g[i] = sum;
    }
    

    std::vector<int> pre(n + 1, 0);
    pre[1] = 1;
    for (int i = 2; i <= n; i ++) {
        if (a[i] - g[i] < a[pre[i - 1]] - g[pre[i - 1]])
            pre[i] = i;
        else 
            pre[i] = pre[i - 1];
    }

    int pos = 0;
    for (int i = 1; i <= n; i++) {
        if (pos == 0 || a[i] - g[i] < a[pos] - g[pos])
            pos = i;
    }
    
    typedef std::pair<ll, int> pli;
    std::priority_queue<pli, std::vector<pli>, std::greater<pli>> pq;

    for (int i = pos + 1; i <= n; i++)
        pq.push({a[i], i});

    // std::cout << pos << ": ";
    ll ans = a[pos] - g[pos];
    std::cout << ans << " ";
    for (int k = 2; k <= n; k++) {
        ll now1 = INF, now2 = INF;
        if (!pq.empty()) {
            now1 = pq.top().first;
        }
        if (pos != 1) {
            int pos_ = pre[pos - 1];
            now2 = g[pos] + a[pos_] - g[pos_];
        }

        if (now1 < now2) {
            // std::cout << pq.top().second << ": ";
            pq.pop();
            ans += now1;
        }
        else {
            int pos_ = pre[pos - 1];
            ans += now2;
            for (int j = pos_ + 1; j < pos; j++)
                pq.push({a[j], j});
            pos = pos_;
            // std::cout << pos << ": ";
        }

    
        std::cout << ans << " ";
    }
    std::cout << "\n";
}

int main() {
    freopen ("D.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int T; std::cin >> T;
    while (T--) solve();
    return 0;
}

F - ministry of prime

Question

给定一个长度为 $n$ 的数组 $a$，修改最少的数字，使得相邻两个元素的和是质数

Solution

考虑到偶数除了 $2$ 以外都不是质数

由此猜想，对于一个三元组 $(x,y,z)$ 如果 $x,y$ 奇偶性相同，则可以找到一个奇偶性和 $x,y$ 不同的 $z$，使得 $x+z,y+z$ 是奇数，用程序验证后发现可行

于是可以定义 $dp[i][0/1/2/3]$ 表示前 $i$ 个数

• $0$：没有修改当前数字
• $1$：把当前数字修改成一个不为 $1$ 的奇数
• $2$：把当前数字修改成偶数
• $3$：把当前数字修改成 $1$

定义出来了，转移方程很容易也写出来了

Code

#include <bits/stdc++.h>

constexpr int N = 1e5 + 5, V = 3e5 + 5;
constexpr int INF = 0x3f3f3f3f;

bool vis[V];

void init() {
    vis[1] = 1;
    for (int i = 2; i < V; i++) {
        for (int j = 2; i * j < V; j++)
            vis[i * j] = 1;
    }
}

bool is_prime(int x) {
    return !vis[x];
}

int dp[N][4];

int main() {
    freopen ("F.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    init();

    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0; dp[1][1] = 1; dp[1][2] = 1; dp[1][3] = 1;
    for (int i = 2; i <= n; i++) {
        
        int tmp = INF;
        if (is_prime(a[i] + a[i - 1])) tmp = std::min(tmp, dp[i - 1][0]);
        if (a[i] % 2 == 1) tmp = std::min(tmp, dp[i - 1][2]);
        if (a[i] % 2 == 0) tmp = std::min(tmp, dp[i - 1][1]);
        if (is_prime(a[i] + 1)) tmp = std::min(tmp, dp[i - 1][3]);
        dp[i][0] = tmp;

        tmp = INF;
        if (a[i - 1] % 2 == 0) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][2] + 1);
        dp[i][1] = tmp;

        tmp = INF;
        if (a[i - 1] % 2 == 1) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][1] + 1);
        tmp = std::min(tmp, dp[i - 1][3] + 1);
        dp[i][2] = tmp;

        tmp = INF;
        if (is_prime(a[i - 1] + 1)) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][2] + 1);
        tmp = std::min(tmp, dp[i - 1][3] + 1);
        dp[i][3] = tmp;
    }
    int ans = std::min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    std::cout << ans << '\n';
    return 0;
}

G - Path

Solution

签到题

Code

#include <bits/stdc++.h>
#define int long long

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int ans = 0;
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n), b(m);
    for (auto &x : a) std::cin >> x;
    for (auto &x : b) std::cin >> x;
    for (int i = 1; i < n; i++)
        ans += abs(a[i] - a[i - 1]);
    for (int i = 1; i < m; i++)
        ans += abs(b[i] - b[i - 1]);
    
    std::cout << ans << '\n';
    return 0;
}

J - Keyi LIkes Reading

Solution

签到题

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 5;
ll n, W, a[MAXN], c[15], f[9000], s[9000];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> W;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        c[a[i] - 1] ++;
    }
    for(int S = 0; S < (1 << 13); S ++){
        for(int i = 0; i < 13; i ++){
            if((S >> i) & 1){
                s[S] += c[i];
            }
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int S = 0; S < (1 << 13); S ++){
        for(int S_ = 0; S_ < (1 << 13); S_ ++){
            if(((S_ | S) == S) && s[S_] <= W){
                f[S] = min(f[S], f[S - S_] + 1);
            }
        }
    }
    cout << f[(1 << 13) - 1] << "\n";
    return 0;
}